#include <vector>  // vector

using namespace std;

class Solution {
   public:
    vector<int> countBits(int n) {
        //每到2的幂，除第一位从0变成1以外，其他位恢复到0的状态
        vector<int> ans = {0};
        int j = 0;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) j = 0;  // 判断是否为2的幂
            ans.push_back(ans[j] + 1);
            ++j;
        }
        return ans;
    }
};